package practice9;

import java.util.Arrays;

public class Demo {

    static final int INF=Integer.MAX_VALUE;
    static int[][] g=new int[1010][1010];
    static int[] dist=new int[1010];
    static int[] path=new int[1010];
    static boolean[] st=new boolean[1010];

    static int n;

    public int dijkstra(){
        Arrays.fill(dist,INF);
        dist[1]=0;      //设置起点
        for(int i=0;i<n-1;i++){
            //找出未标记的、离起点最近的点
            int t=-1;
            for(int j=1;j<=n;j++){
                if(!st[j] && (t==-1 || dist[j]<dist[t])){
                    t=j;
                }
            }
            st[t]=true;
            //更新其邻居的dist和path
            for(int j=1;j<=n;j++){
                if(dist[j]>dist[t]+g[t][j]){
                    dist[j]=dist[t]+g[t][j];
                    path[j]=t;
                }
            }
        }
        if(dist[n]==INF){
            return -1;
        }else{
            return dist[n];
        }
    }

}
